#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//假设使用数组实现栈   数组头部--------数组尾部
//                     栈底           栈顶
//栈顶入数据出数据:O(1)  ==> 尾插尾删

//假设使用链表实现栈  链表头-->   链表尾
//                    栈底         栈顶   ==>此时尾插:O(N) 尾删:O(N)
//                    栈顶         栈底   ==>此时头插:O(1) 头删:O(1)

typedef int DataType;
struct Stack
{
  DataType* a;
  int capacity;
  int top ;//标志栈顶位置  
};
typedef struct Stack Stack;

void Init(Stack* ps);
void push(Stack* ps,DataType x);
void pop(Stack* ps);
bool empty(Stack* ps);
size_t size(Stack* ps);
DataType top(Stack* ps);
void Destory(Stack* ps);